package com.hyc.DataStructure.Queue;

import java.util.Scanner;

/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.Queue
 * @className: CircleArrayQueueDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2021/12/16 16:28
 * @version: 1.0
 */
public class CircleArrayQueueDemo {
    public static void main(String[] args) {
        System.out.println("测试环形队列");
//创建一个队列 这里空间为4 最大有效空间为3 留出一个空间作为约定
        CircleArrayQueue queue = new CircleArrayQueue(4);
        char key = ' '; //接收用户输入
        Scanner scanner = new Scanner(System.in);//
        boolean loop = true;
//输出一个菜单
        while (loop) {
            System.out.println("s(show): 显示队列");
            System.out.println("e(exit): 退出程序");
            System.out.println("a(add): 添加数据到队列");
            System.out.println("g(get): 从队列取出数据");
            System.out.println("h(head): 查看队列头的数据");
            key = scanner.next().charAt(0);//接收一个字符
            switch (key) {
                case 's':
                    queue.showQueue();
                    break;
                case 'a':
                    System.out.println("输出一个数");
                    int value = scanner.nextInt();
                    queue.addQueue(value);
                    break;
                case 'g': //取出数据
                    try {
                        int res = queue.getQueue();
                        System.out.printf("取出的数据是%d\n", res);
                    } catch (Exception e) {
// TODO: handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h': //查看队列头的数据
                    try {
                        int res = queue.headQueue();
                        System.out.printf("队列头的数据是%d\n", res);
                    } catch (Exception e) {
// TODO: handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e': //退出
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出~~");
    }
}

/** 环形队列
 * 思路变化：
 * 之前的队列有问什么问题所在
 * 问题分析并优化
 *1) 目前数组使用一次就不能用， 没有达到复用的效果
 *2) 将这个数组使用算法，改进成一个环形的队列 取模：%
 * 思路如下 ：
 * 1.front变量的含义做一个调整：front就指向队列的第一个元素，也就是说arr(front]就是队列的第一个元素
 * front的初始值
 * 2.rear变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置.因为希望空出一个空间做为约定.
 * rear的初始值=0
 * 3.当队列满时，条件是（rear+1)%maxSize=front【满】
 * 4.对队列为空的条件，rear==front空
 * 5.当我们这样分析，队列中有效的数据的个数（rear+maxSize-front)%maxSize//rear=1front=0
 * 6.我们就可以在原来的队列上修改得到，一个环形队列
 *
 * */

class CircleArrayQueue {
    //队列最大上限
    private int MaxSize;
    //队列尾部 思路发生变化这次我们的队尾值变化为0指向队列最后一位的前一位
    private int rear;
    //队列头部 思路变化 指向队头的第一位 也就是下标 为 0   
    private int front;
    //存放队列数据的数组
    private int[] ArrayQueue;

    /**
     * @author 冷环渊 Doomwatcher
     * @context: 初始化构造队列，初始化队列和头尾值向
     * 这里为什么没有初始化队头队尾，因为默认 = 0
     * @date: 2021/12/16 14:30
     * @param maxSize
     * @return:
     */
    public CircleArrayQueue(int maxSize) {
        // 获取最大值
        this.MaxSize = maxSize;
        //初始化 队列
        ArrayQueue = new int[MaxSize];
    }

    /**
     * @author 冷环渊 Doomwatcher
     * @context:
     * 这里思路变化，因为我们要做环形队列这里我们有一个位置是动态变化的所以我们需要更新计算是否队列已满的方法
     * @date: 2021/12/16 14:30
     * @param
     * @return: boolean
     */
    public boolean isfull() {
        return (rear + 1) % MaxSize == front;
    }

    /**
     * @author 冷环渊 Doomwatcher
     * @context: 判断队列是否是空的
     * @date: 2021/12/16 14:32
     * @param
     * @return: boolean
     */
    public boolean isemity() {
        return rear == front;
    }

    /**
     * @author 冷环渊 Doomwatcher
     * @context:
     * 加入数据我们也要发生变化 这里我们用的是环形了
     * rear 的后移不再是最后一位，可能会出现越界的问题
     * （rear+1）%maxSize
     * @date: 2021/12/16 14:34
     * @param value
     * @return: void
     */
    public void addQueue(int value) {
        if (isfull()) {
            System.out.println("队列已满 不能加入更多的数据");
            return;
        }
        //赋值
        ArrayQueue[rear] = value;
        //考虑用取模来后移 rear
        rear = (rear + 1) % MaxSize;
    }

    /**
     * @author 冷环渊 Doomwatcher
     * @context:
     * 为什么不用 ++了呢 因为我们是环形 一定会出现越界，这里考虑取模动态的算出后移的位置
     * @date: 2021/12/16 14:37
     * @param
     * @return: void
     */
    public int getQueue() {
        if (isemity()) {
            throw new RuntimeException("该队列是空的 无法获取到内容");
        }
        /*
         * 1，我们这次的思路是front代表的是队列的第一个下标
         * 2. 用临时变量来拿出 当前的值
         * 3.后移front 返回值
         * */
        int value = ArrayQueue[front];
        front = (front + 1) % MaxSize;
        return value;
    }

    /**
     * @author 冷环渊 Doomwatcher
     * @context:
     * 遍历环形队列 输出 这里我们不再是遍历数组长度了
     * 我们需要求出有效的数量
     * @date: 2021/12/16 14:42
     * @param
     * @return: void
     */
    public void showQueue() {
        if (isemity()) {
            System.out.println("队列没有可以遍历的数值");
        }
        //这里我们因该是从 front 开始遍历
        for (int i = front; i < front + Size(); i++) {
            //这里下标我们选择取模 应为是环形的会出现越界的情况，所以我们使用取模运算
            System.out.printf("arrQueue[%d]: %d\n", i % MaxSize, ArrayQueue[i % MaxSize]);
        }
    }

    /*编写一个求出队列有效数据数量的放啊*/
    public int Size() {
        /* 取模思路套用
         * 1. rear = 1
         * 2. front = 0
         * 3. maxSize = 3
         * （1+3-0）%3 = 1 应为算出来是下标 所以我们这里有两个有效数据 0，1
         * */
        return (rear + MaxSize - front) % MaxSize;
    }

    /**
     * @author 冷环渊 Doomwatcher
     * @context:这里我们和上一个遍历方法一样 只是展示数据并不是去出数据
     * 这里不再是 front-1 应为 front此时默认就是0
     * @date: 2021/12/16 14:45
     * @param
     * @return: void
     */
    public int headQueue() {
        if (isemity()) {
            throw new RuntimeException("没有头数据");
        }
        return ArrayQueue[front];
    }
}